/**
 * [51] N 皇后
 *
 * @format
 * @lc app=leetcode.cn id=51 lang=javascript
 */

// @lc code=start
/**
 * @param {number} n
 * @return {string[][]}
 */
// 空间优化
var solveNQueens = function (n) {
    // 结果数组
    const results = []
    // 备忘录：攻击范围标记
    const memo = {
        rows: Array(n)
            .fill(0)
            .map((e, i) =>
                Array(n)
                    .fill(0)
                    .map((e, j) => (j === i ? "Q" : "."))
                    .join("")
            ),
        // 列
        cols: Array(n).fill(0),
        // 主对角线
        main: Array(2 * n - 1).fill(0),
        // 副对角线
        oppo: Array(2 * n - 1).fill(0),
        // 结果栈
        posi: []
    }
    function setQueens(memo, n, i, results) {
        if (i === n - 1) {
            for (let j = 0; j < n; j++) {
                if (memo.cols[j] || memo.main[i - j + n - 1] || memo.oppo[i + j]) continue
                else {
                    memo.posi.push(memo.rows[j])
                    results.push([...memo.posi])
                    memo.posi.pop()
                }
            }
        } else {
            for (let j = 0; j < n; j++) {
                if (memo.cols[j] || memo.main[i - j + n - 1] || memo.oppo[i + j]) continue
                else {
                    memo.cols[j] = 1
                    memo.main[i - j + n - 1] = 1
                    memo.oppo[i + j] = 1
                    memo.posi.push(memo.rows[j])
                    setQueens(memo, n, i + 1, results)
                    memo.posi.pop()
                    memo.cols[j] = 0
                    memo.main[i - j + n - 1] = 0
                    memo.oppo[i + j] = 0
                }
            }
        }
    }
    setQueens(memo, n, 0, results)
    return results
}
// Accepted
// 9/9 cases passed (69 ms)
// Your runtime beats 79.32 % of javascript submissions
// Your memory usage beats 12.66 % of javascript submissions (55.2 MB)
// 递归回溯
/* var solveNQueens = function (n) {
    const results = []
    // 初始化棋盘
    const chessBoard = Array(n)
        .fill(0)
        .map(() => Array(n).fill(0))
    // 攻击方向：
    // # 0b001 右下
    // # 0b010 下
    // # 0b100 左下
    // 放置皇后
    function placeQueen(chessBoard, row, results) {
        // 延伸攻击范围至下一行
        if (row < n - 1) {
            for (let col = 0; col < n; col++) {
                // 右下
                if (col < n - 1 && chessBoard[row][col] & 1) chessBoard[row + 1][col + 1] |= 1
                // 正下
                if (chessBoard[row][col] & 2) chessBoard[row + 1][col] |= 2
                // 左下
                if (col > 0 && chessBoard[row][col] & 4) chessBoard[row + 1][col - 1] |= 4
            }
        }
        for (let col = 0; col < n; col++) {
            // 剪枝
            // if (row == 0 && col >= n / 2) break
            // 在棋盘安全块放置新皇后
            if (chessBoard[row][col] == 0) {
                chessBoard[row][col] = "Q"
                if (row < n - 1) {
                    // 延伸新皇后攻击范围至下一行
                    if (col < n - 1) chessBoard[row + 1][col + 1] |= 1
                    chessBoard[row + 1][col] |= 2
                    if (col > 0) chessBoard[row + 1][col - 1] |= 4
                    // 放置下一行
                    placeQueen(chessBoard, row + 1, results)
                    // 撤销新皇后攻击范围
                    if (col < n - 1) chessBoard[row + 1][col + 1] &= 6
                    chessBoard[row + 1][col] &= 5
                    if (col > 0) chessBoard[row + 1][col - 1] &= 3
                } else {
                    const result = chessBoard.map(row => {
                        let temp = ""
                        for (let c of row) c == "Q" ? (temp += "Q") : (temp += ".")
                        return temp
                    })
                    results.push(result)
                }
                // 撤回新皇后
                chessBoard[row][col] = 0
            }
        }
        if (row < n - 1) {
            for (let col = 0; col < n; col++) {
                chessBoard[row + 1][col] = 0
            }
        }
    }
    placeQueen(chessBoard, 0, results)
    return results
} */
// debugger
// let n = 4
// const results = solveNQueens(n)
// console.log(results)
// @lc code=end
